package go_leetcode

// func maxSubArray(nums []int) int {
// 	max := nums[0]
// 	for i := 1; i < len(nums); i++ {
// 		if nums[i] + nums[i - 1] > nums[i] {
// 			nums[i] += nums[i - 1]
// 		}
// 		if nums[i] > max {
// 			max = nums[i]
// 		}
// 	}
// 	return max
// }
func maxSubArray(nums []int) int {
	if len(nums) == 1 {
        return nums[0]
    }
    dp := make([]int, len(nums))
    dp[0] = nums[0]
    res := dp[0]
    for i := 1; i < len(nums); i++ {
        dp[i] = max(dp[i-1] + nums[i], nums[i])
        if dp[i] > res {
            res = dp[i]
        }
    }
    return res
}

